/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function (heights) {
  let m = heights.length // 获得这个数组的行数
  let n = heights[0].length // 获得这个数组的列数
  let effortTo = new Array(m).fill(0).map(() => new Array(n).fill(Infinity)) // 定义从0,0 到i,j的最小体力消耗是 effortTo[i][j]
  effortTo[0][0] = 0 // 起点到起点的距离是0
  let pq = new myPriorityQueue()
  pq.enqueue(new State(0, 0, 0), 0) // 这个元素的坐标是0,0 距离是0  权重是0
  while (!pq.isEmpty()) {
    let curState = pq.dequeue().element // 弹出这个元素
    let curX = curState.x
    let curY = curState.y
    let curEffortFromStart = curState.effortFromStart // 获得xy坐标和距离
    if (curX === m - 1 && curY === n - 1) {
      // 到达最后一个元素 直接返回
      return curEffortFromStart
    }
    if (curEffortFromStart > effortTo[curX][curY]) {
      continue
    }
    // 将curX和curY的相邻坐标装入队列
    for (let neighbor of adj(heights, curX, curY)) {
      let nextX = neighbor[0]
      let nextY = neighbor[1]
      // 计算从curX,curY到nextX,nextY的消耗
      let effortToNextNode = Math.max(
        effortTo[curX][curY],
        Math.abs(heights[curX][curY] - heights[nextX][nextY])
      )
      // 更新dp table
      if (effortTo[nextX][nextY] > effortToNextNode) {
        effortTo[nextX][nextY] = effortToNextNode
        pq.enqueue(new State(nextX, nextY, effortToNextNode), effortToNextNode)
      }
    }
  }
  return -1 // 正常情况下不会到达的时候 就return -1
};
function adj (matrix, x, y) {
  let dirs = [[1, 0], [-1, 0], [0, -1], [0, 1]]
  let m = matrix.length
  let n = matrix[0].length
  let neighbors = []
  for (let dir of dirs) {
    let nx = x + dir[0]
    let ny = y + dir[1] // 新的x和y
    if (nx >= m || nx < 0 || ny >= n || ny < 0) {
      continue // 越界就下一个
    }
    neighbors.push([nx, ny])
  }
  return neighbors // 返回邻居节点
}
class State {
  constructor(x, y, effortFromStart) {
    this.x = x
    this.y = y // 获得这个节点的xy坐标
    this.effortFromStart = effortFromStart // 从起点到节点的距离
  }
}
function dijkstra (start, end, graph) {
  let n = graph.length // 获得图的长度
  let distTo = new Array(n).fill(Infinity) // 初始化这个从起点到该节点的路径都是最大值
  distTo[start] = 0 // 起点到起点是0
  let pq = new myPriorityQueue() // 创建一个优先级队列
  pq.enqueue(new State(start, 0), 0) // 这个的优先级就是这个的distFromStart
  while (!pq.isEmpty()) { // 如果队列不是空的话
    let curState = pq.dequeue().element // 队列弹出
    let curNodeId = curState.id // 获得弹出的元素的id
    let curDistFromStart = curState.distFromStart // 获得从起点到这个元素的距离
    if (curNodeId === end) {
      return curDistFromStart // 如果这个当前的id是结尾的id 那么直接返回起点到这个元素的距离就好了
    }
    if (curDistFromStart > distTo[curNodeId]) {
      // 如果从起点到这个元素的距离 大于distTo数组中当前节点的距离 就直接进行下一次循环
      continue
    }
    for (let neighbor of graph[curNodeId]) { // 拿出这个节点所有的邻居
      let nextNodeId = neighbor[0] // 获得这个邻居的id
      let distToNextNode = distTo[curNodeId] + neighbor[1] // 计算从起始节点到这个节点的最短距离
      if (distTo[nextNodeId] > distToNextNode) { // 如果现在的下一个节点的最短距离 大于从起始节点到该节点的距离
        distTo[nextNodeId] = distToNextNode
        let nextState =  // 生成下一个的
          pq.enqueue(new State(nextNodeId, distToNextNode), distToNextNode) // 将当前的节点放入优先级队列 此时的权重是distToNextNode
      }
    }
  }
  return distTo // 返回结果数组 表示起点到各点的最短权重
}
//封装优先级队列，priority越小，优先级越高
function myPriorityQueue () {
  //存放每一个插入元素QueueElement
  this.items = [];
  //定义内部类--封装插入元素
  function QueueElement (element, priority) {
    this.element = element;
    this.priority = priority;
  }
  //实现插入操作
  myPriorityQueue.prototype.enqueue = function (element, priority) {
    var qe = new QueueElement(element, priority);
    if (this.items.length === 0) {
      this.items.push(qe);
    } else {
      var flag = false; //记录元素是否插入，没有就插入到items最后
      for (var i = 0; i < this.items.length; i++) {
        if (priority < this.items[i].priority) {
          this.items.splice(i, 0, qe);
          flag = true;
          break;
        }
      }
      if (!flag) {	//没有就插入到items最后
        this.items.push(qe);
      }
    }
  }

  //2.将元素从队列中移除
  myPriorityQueue.prototype.dequeue = function () {
    return this.items.shift();
  }
  //3.查看队列中第一个元素
  myPriorityQueue.prototype.front = function () {
    return this.items[0];
  }
  //4.查看队列是否为空
  myPriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0;
  }
  //5.查看队列中元素的个数
  myPriorityQueue.prototype.size = function () {
    return this.items.length;
  }
  //6.toString
  myPriorityQueue.prototype.toString = function () {
    var result = '';
    for (var i = 0; i < this.items.length; i++) {
      result += this.items[i].element + '---' + this.items[i].priority + ' ';
    }
    return result;
  }
}